“Network” as a term is potentially capable of being applied to describe relationships between entities. For example, in FIG. 1, there is shown a network indicated generally by 10. The network 10 includes a plurality of entities 20 and relationships 30 which associate the entities 20 relative to one another; the entities 20 are conveniently referred to as being “nodes”, and the relationships as being “links”.
The entities 20 can be either real physical objects or virtual objects. For example, the real physical objects include communication system nodes, cities, buildings, electricity power generators, and people. Virtual objects include, for example, collections of data, financial share holdings, personal relationships and bank accounts. The relationships 30 can also be either real physical components or virtual components. For example, the real physical components include optical fiber communication links, roads, and electrical power distribution cables. The virtual components include, for example, legal relationships, legal rights, similarities in data structures, and money. The network 10 is potentially highly complex with millions of the entities 20 being present and a correspondingly many millions of relationships 30 existing between the entities 20.
There arises a need to analyze networks, for example for purposes of searching or navigating within the networks, for controlling the networks, for controlling information flow within the networks, for reconfiguring the networks to mention a few examples. Methods of analyzing networks are known. One known method employs a “topographical” approach, wherein a network is visualized in a form akin to a 3-dimensional relief. This method employs an Eigenvector centrality (EVC) of a given node of a network to represent a degree to which the given node is connected or related to other nodes of the network. The network, when represented by Eigenvector centrality values (EVC) of its nodes, will include one or more nodes which have a peak maximum EVC value for the network, and potentially none, one or more nodes which have EVC values which are less than the peak maximum EVC value and which correspond to none, one or more local maximum EVC values within the network. The one or more nodes corresponding to the one or more local maximum EVC values define one or more corresponding “regions” of the network. In a network, the number of such “regions” found is thus equal to a number of local EVC maxima. The method employs a simple rule for assigning non-centre nodes, namely each node belongs to a same region as its neighbor having a highest EVC. This simple rule will be referred to as a “steepest-ascent rule”.
A method for analyzing networks utilizing the aforementioned “topographical” approach is described by the present inventors in a published International PCT patent application WO 2007/049972. The method described in the PCT patent application is based on utilizing a steepest ascent graph (SAG). In FIG. 1, the aforesaid network 10 includes a plurality of nodes 20. The nodes 20 of the network 10 are here depicted with a topological map with iso-EVC value curves denoted by 40. The Eigenvector centrality (EVC) of each node 20 is conveniently, for topographical visualization purposes, interpreted to be an “altitude” of the node 20, and each region of nodes 20 is interpreted to be a “mountain”. For each region of nodes 20, a node in the region having a highest EVC is taken to be a centre of the region, namely in a manner akin to a peak of a mountain. The nodes in each region are mutually connected by a plurality of association links represented by thin lines 30, but only links that connect a node with its neighbor having highest EVC as represented by thick lines 50 are included for deriving a SAG. These links, as represented by the thick lines 50 for the SAG, correspond to most likely paths, for example for information flow, towards the central nodes of regions. Conveniently, each region can be divided into sub-regions, wherein each neighbor of a centre node in a region is defined as being a sub-region centre node. The aforesaid method is thus susceptible to being used to analyze a network of nodes, and to find central nodes therein defining a centre of each sub-region. By applying the method to analyze a network comprising interconnected nodes, it is possible for analysis purposes to sub-divide the network into suitable sub-regions.
The aforesaid “topographical” approach has shown itself to be useful in analyzing networks, for example as a tool for understanding spreading of information within networks of interconnected nodes. As a consequence of such analysis, networks of interconnected nodes are susceptible to being reconfigured to preferentially hinder or enhance, depending on requirements, flow of information therein.
However, it is found that the “topographical” approach based on EVC, for example as elucidated in a published International PCT patent application no. WO 2007/049972, does not reveal all inherent nodal structures in all types of networks including interconnected nodes. In consequence, the aforesaid method applied in certain types of networks to control information flow therein does not provide optimal analysis, monitoring and/or control of such networks.